#include <iostream>
#include <vector>
using namespace std;

size_t Binary_search(vector<int>& low, int right, int num){
	int left = 1, mid;
	// 二分查找v中第一个>=num的元素下标
	while (left <= right){
		mid = ((right-left)>>1)+left;
		if (low[mid] < num)
            left = mid + 1;
		else
			right = mid - 1;
	}
	return left;
}

size_t LIS(vector<int>& v){
    vector<int> low(v.size()+1, 0);
    size_t retLen = 1;
    low[retLen] = v[0];
    for(size_t i = 1; i < v.size(); ++i){
        if(low[retLen] < v[i])
            low[++retLen] = v[i];
        else
            low[Binary_search(low, retLen, v[i])] = v[i];//二分查找
    }
    return retLen;
}

int main()
{
	size_t n;
	while (cin >> n){
		vector<int> v(n);
		for (size_t i = 0; i < n; ++i)
			cin >> v[i];
                   
		cout << LIS(v) << endl;
	}
	return 0;
}